Asymptotic Notation
Q2.
Let f and g be functions of natural numbers given by f(n)=n and g(n)=n^2. Which of the following statements is/are TRUE?Q3.
There are n unsorted arrays: A_1,A_2,...,A_n. Assume that n is odd. Each of A_1,A_2,...,A_n contains n distinct elements. There are no common elements between any two arrays. The worst-case Asymptotic Notation of computing the median of the medians of A_1,A_2,...,A_n is ________ .Q4.
Consider functions Function 1 and Function 2 expressed in pseudocode as follows:Let f_1(n) and f_2(n) denote the number of times the statement "x = x + 1" is executed in Function 1 and Function 2, respectively. Which of the following statements is/are TRUE?Q5.
Consider the following C function int fun (int n) { int i, j; for (i = 1; i < = n; i++) { for (j = 1 ; j < n ; j+=i) { printf ("%d %d , i, j ) ; } } } Asymptotic Notation of fun in terms of \theta notation isQ7.
What is the complexity of the following code? sum=0; for(i=1;i<=n;i*=2) for(j=1;j<=n;j++) sum++;Which of the following is not a valid string?Q8.
Consider the following three functions. f_1=10^n\; f_2=n^{\log n}\;f_3=n^{\sqrt {n}} Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?Q9.
Consider the following functions from positive integers to real numbers: 10,\sqrt{n},n, log_{2}n,\frac{100}{n}. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:Q10.
In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E|=m and |V|=n, and the memory size is not a constraint, what is the Asymptotic Notation of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?